package array.leetcode.easy;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author bruin_du
 * @description 和为s的连续正数序列
 * @date 2022/6/10 14:42
 **/
public class Offer57II_FindContinuousSequence {
    public int[][] findContinuousSequence(int target) {
        //方法一：暴力法
        method1(target);

        //方法二:数学公式计算
        method2(target);

        //方法三:基于双指针的滑动窗口
        return method3(target);
    }

    private int[][] method1(int target) {
        int[] arr = new int[target / 2 + 2];
        List<int[]> list = new ArrayList<>();
        for (int i = 0; i < arr.length; i++) {
            arr[i] = i;
        }
        for (int i = 1; i < arr.length; i++) {
            int sum = 0;
            boolean flag = false;
            int j = i;
            for (; j < arr.length; j++) {
                sum += j;
                if(sum > target){
                    break;
                }else if(sum == target){
                    flag = true;
                    break;
                }
            }
            if(flag){
                list.add(Arrays.copyOfRange(arr,i,j + 1));
            }
        }
        return list.toArray(new int[list.size()][]);
    }

    private int[][] method2(int target) {
        double j = 0.0;
        List<int[]> list = new ArrayList<>();
        for (int i = 1; i <= target / 2; i++) {
            j = (-1 + Math.sqrt(1 - 4 * (i - (double)i * i - 2 * target))) / 2;
            if(j == (int)j){
                int[] arr = new int[(int)j - i + 1];
                for (int i1 = i; i1 <= (int)j; i1++) {
                    arr[i1 - i] = i1;
                }
                list.add(arr);
            }
        }
        return list.toArray(new int[list.size()][]);
    }

    private int[][] method3(int target) {
        int left = 1,right = 2,sum = 3;
        List<int[]> list = new ArrayList<>();
        while(left < right) {
            if(target == sum) {
                int[] arr = new int[right - left + 1];
                for (int i = left; i <= right; i++) {
                    arr[i - left] = i;
                }
                list.add(arr);
            }
            if(target > sum){
                right++;
                sum += right;
            }else{
                sum -= left;
                left++;
            }
        }
        return list.toArray(new int[list.size()][]);
    }
}
